#include <vector>
#include <string>

using namespace std;

// 岛屿数量
// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
// 此外，你可以假设该网格的四条边均被水包围
// 测试链接 : https://leetcode.cn/problems/number-of-islands/

class Solution 
{
private:
    static const int MAXSIZE = 100001;
    int father[MAXSIZE];
    int sets; 

    void Build(vector<vector<char>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        sets = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == '1')
                {
                    // 记 pos = i * n + j，则 i = pos / n，j = pos % n
                    // 这是一个常用的坐标压缩技巧
                    father[i * n + j] = i * n + j;
                    ++sets;
                }
            }
        }
    }

    int Find(int i)
    {
        return i == father[i] ? i : father[i] = Find(father[i]);
    }

    void Union(int x, int y)
    {
        int fx = Find(x);
        int fy = Find(y);
        if(fx != fy)
        {
            father[fx] = fy;
            --sets;
        }
    }

public:
    // 并查集的做法
    int numIslands(vector<vector<char>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        Build(grid);
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == '1')
                {
                    // 向上合并
                    if(i > 0 && grid[i - 1][j] == '1')
                    {
                        Union(i * n + j, (i - 1) * n + j);
                    }
                    // 向左合并
                    if(j > 0 && grid[i][j - 1] == '1')
                    {
                        Union(i * n + j, i * n + j - 1);
                    }
                }
            }
        }
        return sets;
    }
};